Grafisch-geometrische Algorithmen lösen Probleme, die auf geometrische Objekte wie Punkte, Linien, Flächen und Körpern im zwei- oder mehrdimensionalen Raum basieren (Algorithmische Geometrie, computational geometry). Diese Algorithmen und ihre zugrundeliegenden Datenstrukturen werden unter anderen in den Bereichen der Computergrafik, Robotik und Geoinformationssysteme angewendet.
Studenten lernen typische Algorithmen aus der Algorithmischen Geometrie, deren Enturfsprinzipien und Anwendungsbereiche kennen.
Sie werden befähigt die Algorithmen hinsichtlich ihrer Korrektheit, des Resourcenverbrauchs und Robustheit zu untersuchen und zu vergleichen.
Unter anderem werden folgenden Probleme exemplarisch behandelt:
Berechnung konvexer Hüllen, Schnitt- und Abstandsprobleme, Triangulierung von Polygonen, Geometrische Datenstrukturen wie kd-Bäume.
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: "Computational Geometry: Algorithms and Applications", 2008, 3. Auflage, Springer-Verlag
Franco P. Preparata, Michael Shamos: "Computational Geometry: An Introduction", 1985, Springer-Verlag
Spezielle weiterführende Literatur wird in der Vorlesung bekannt gegeben.
